AtCoder Beginner Contest 313

To Be Saikyo

简单模拟。

public static void solve() {
    int n = io.nextInt(), x = io.nextInt(), max = 0;
    for (int i = 1; i < n; i++) {
        max = Math.max(max, io.nextInt());
    }
    io.println(Math.max(max - x + 1, 0));
}

Who is Saikyo?

如果 \(A\) 比 \(B\) 强，则让 \(B\) 的入度加一，最后入度为零的程序员就是最强的，如果多于一个那么返回 \(-1\) 。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] in = new int[n + 1];
    for (int i = 0; i < m; i++) {
        int u = io.nextInt(), v = io.nextInt();
        in[v]++;
    }
    int ans = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            ans = i;
            cnt++;
        }
    }
    io.println(cnt == 1 ? ans : -1);
}

Approximate Equalization 2

假设我们将数组 \(A\) 执行最少操作后得到数组 \(B\) ，那么 \(\frac{\sum_{i=1}^{N}|A_{i}-B{i}|}{2}\) 就是最小操作次数，因为必定有 \(\sum_{i=1}^{N}A_{i}=\sum_{i=1}^{N}B_{i}\) ，所以上述公式一定可以被二整除。题目要求 \(B\) 的最大值和最小值的差最多为一，那么 \(B\) 一定由 \(N-r\) 个 \(p\) ，以及 \(r\) 个 \(p+1\) 组成，其中 \(p=\frac{\sum_{i=1}^{N}B_{i}}{N},r=\sum_{i=1}^{N}B_{i}\bmod N\) 。然后问题就变为如何组织 \(A_{i}\) 和 \(B_{i}\) 的对应关系，使得 \(\frac{\sum_{i=1}^{N}|A_{i}-B{i}|}{2}\) 最小。显然对数组 \(A\) 进行升序排序，那么数组 \(B\) 的 \(N-r\) 个 \(p\) 对应 \(A\) 的前 \(N-r\) 个元素，数组 \(B\) 的 \(r\) 个 \(p+1\) 对应 \(A\) 的后 \(r\) 个元素，这样排列会使得操作次数最小。

PS：比赛时没什么思路，猜了个平均数，然后没有排序通过遍历比较大小来计算操作次数，结果和正解殊途同归了。

public static void solve() {
    int n = io.nextInt();
    long sum = 0L;
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = io.nextInt();
        sum += arr[i];
    }
    // 可以替换为快速选择
    Arrays.sort(arr);
    long ans = 0L, p = sum / n, r = sum % n;
    for (int i = 0; i < n; i++) {
        ans += Math.abs(arr[i] - (p + (i >= n - r ? 1 : 0)));
    }
    io.println(ans / 2);
}

Odd or Even

每次查询的返回值可以看作 \(A_{x_{1}}\oplus A_{x_{2}}\oplus \cdots \oplus A_{x_{k}}\) ，所以我们可以首先对前 \(k+1\) 个数进行 \(k+1\) 次查询，然后把所有查询结果异或，可以得到前 \(k+1\) 个数的异或值（因为在 \(k+1\) 次查询中，每个数出现 \(k\) 次，并且 \(k\) 是奇数），将该异或值分别与之前的查询结果异或，可以得到前 \(k+1\) 个数的值。之后的操作类似，就是查询然后异或，得到后面的所有值。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), xor = 0;
    List<Integer> aux;
    int[] ans = new int[n];
    for (int i = 0; i <= k; i++) {
        aux = new ArrayList<>();
        for (int j = 0; j <= k; j++) {
            if (i != j) aux.add(j);
        }
        ans[i] = query(aux);
        xor ^= ans[i];
    }
    for (int i = 0; i <= k; i++) ans[i] ^= xor;
    xor ^= ans[k] ^ ans[k - 1];
    aux = new ArrayList<>();
    for (int i = 0; i < k; i++) aux.add(i);
    for (int i = k + 1; i < n; i++) {
        aux.set(k - 1, i);
        ans[i] = query(aux) ^ xor;
    }
    io.print("! ");
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

private static int query(List<Integer> aux) {
    io.print("? ");
    for (int x : aux) {
        io.print(x + 1 + " ");
    }
    io.println();
    io.flush();
    return io.nextInt();
}